#define _CRT_SECURE_NO_WARNINGS 1

using namespace std;
#include<vector>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

int sumOfLeftLeaves(TreeNode* root) {
    if (root == nullptr)
        return 0;

    int sum = 0;
    if (root->left && root->left->left == nullptr && root->left->right == nullptr)
        sum += root->left->val;

    return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}

class Solution
{
public:
    int ret;
    int height;
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0);
        return ret;
    }

    void dfs(TreeNode* root, int h)
    {
        if (root == nullptr)
            return;
        h++;
        dfs(root->left, h);
        dfs(root->right, h);
        if (h > height)
        {
            ret = root->val;
            height = h;
        }
    }
};

int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n + 1, 0);
    vector<int> right(n + 1, 0);


    for (int i = 1; i < n; i++)
        left[i] = left[i - 1] + nums[i - 1];

    for (int i = n - 2; i >= 0; i--)
        right[i] = right[i + 1] + nums[i + 1];

    for (int i = 0; i < n; i++)
    {
        if (left[i] == right[i])
            return i;
    }
    return -1;
}

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n + 1);
    vector<int> right(n + 1);
    vector<int> ret(n);
    left[0] = 1;
    right[n - 1] = 1;

    for (int i = 1; i < n; i++)
        left[i] = left[i - 1] * nums[i - 1];

    for (int i = n - 2; i >= 0; i--)
        right[i] = right[i + 1] * nums[i + 1];

    for (int i = 0; i < n; i++)
        ret[i] = left[i] * right[i];

    return ret;
}

void sortColors(vector<int>& nums) {
    int n = nums.size();
    int begin = 0, end = n - 1;
    my_sort(nums, begin, end);
}

void my_sort(vector<int>& nums, int begin, int end)
{
    if (begin >= end)
        return;
    int slow = begin, fast = slow + 1;
    int key = begin;
    while (fast <= end)
    {
        if (nums[fast] < nums[key] && ++slow != fast)
        {
            swap(nums[fast], nums[slow]);
        }
        fast++;
    }

    swap(nums[slow], nums[key]);
    key = slow;
    //[begin,key-1] key [key+1,end]
    my_sort(nums, begin, key - 1);
    my_sort(nums, key + 1, end);
}


int getMid(vector<int> nums, int left, int right)
{
    int mid = (left + right) / 2;

    if (nums[left] < nums[right])
    {
        if (nums[mid] > nums[right])
            return right;
        else if (nums[mid] < nums[left])
            return left;
        else
            return mid;
    }
    else
    {
        if (nums[mid] > nums[left])
            return left;
        else if (nums[mid] < nums[right])
            return right;
        else
            return mid;
    }
}

void my_sort(vector<int>& nums, int begin, int end)
{
    if (begin >= end)
        return;
    int slow = begin, fast = slow + 1;
    int mid = getMid(nums, begin, end);
    swap(nums[begin], nums[mid]);
    int key = begin;
    while (fast <= end)
    {
        if (nums[fast] < nums[key] && ++slow != fast)
        {
            swap(nums[fast], nums[slow]);
        }
        fast++;
    }

    swap(nums[slow], nums[key]);
    key = slow;
    //[begin,key-1] key [key+1,end]
    my_sort(nums, begin, key - 1);
    my_sort(nums, key + 1, end);
}

vector<int> sortArray(vector<int>& nums) {
    int n = nums.size();
    int begin = 0, end = n - 1;
    my_sort(nums, begin, end);
    return nums;
}